Recursion

In programming, recursion means a function that calls itself (usually with a different input) to solve a problem by breaking it down into smaller, similar sub-problems. It's usually possible to convert a recursive function into an iterative one, and vice versa.

Recursion is particularly useful when:

• The problem can be broken down into smaller versions of itself
• You're working with tree-like or nested data structures
• The code needs to maintain a stack of previous states
• The recursive solution is significantly clearer than the iterative one

However, recursion might not be the best choice when:

• The recursive depth could be very large (risking stack overflow)
• Performance is critical (due to function call overhead)
• The problem can be solved just as clearly with iteration"

Every recursive solution needs two key components:

1. A base case that stops the recursion.
   • If there is no base case in recursion, the recursive case would execute forever resulting in a stack overflow error.
2. A recursive case that breaks the problem into a smaller version of itself.

There are two types of recursion, one branch and multi-branch.

I. One-branch Recursion

1. Factorial

If we want to compute n! (n-factorial), we can use recursion. The formula for n! is: n * (n - 1) * (n - 2) * ... * 1. e.g. 5! = 5 * 4 * 3 * 2 * 1 = 120.

1. Recursive case: 5! can be broken down into 5 * 4!. 4! can be broken down into 4 * 3! can so on.
2. Base case: When n = 0 or n = 1. The result of 0! and 1! is 1.

Example: Factorial Tree Recursion

# Recursive implementation of n! (n-factorial) calculation
def factorial(n):
    # Base case: n = 0 or 1
    if n <= 1:
        return 1

    # Recursive case: n! = n * (n - 1)!
    return n * factorial(n - 1)

• When the code reaches the last line with the initial input of 5, we get 5 * factorial(4)
  • Which then starts executing the function again from the first line with input 4, so we get 4 * factorial(3)
    • Then 3 * factorial(2) is executed
      • Lastly 2 * factorial(1) → base case is reached (n = 1).

→ When we trigger the base case, we move back "up" the recursion tree because now we have to "piece" together the answers to our sub-problems to get to the final solution.

When the function is called with 1 as the input, 1 is returned, and now it can be multiplied by 2, which will result in 2, which is the answer to 2.

• Now, we compute 3 * factorial(2), which results in 6, then 4 * factorial(3), which is 24, and finally 5 * factorial(4), which is 120 - the final answer to 5!.

We took the original problem factorial(5) and broke it down into smaller sub-problems, and by combining the answer to those subproblems, we were able to solve the original problem.

2. Iteration and Recursion

Most recursive algorithms and can be written iteratively.

n = 5
res = 1
while n > 1:
    res = res * n
    n -= 1

The iterative implementation is much simpler than the recursive one in this case, but that's not always the case. Recursion will be especially useful when we start learning about trees.

Summary

a. Time Complexity

In total, n calls are being made to the factorial function, where each function call is O(1), making the total time complexity O(n).

b. Space Complexity

While we aren't using any data structures, recursion operates off of an implicit stack, known as the function call stack. That is how we are able to return from one function call to the previous one. Since there are n recursive calls, there will be n function calls placed on the stack, which results in O(n) space.

II. Two-branch Recursion

1. Fibonacci Sequence

The Fibonacci sequence is a set of numbers that starts with 0 and 1, and each subsequent number is the sum of the two preceding numbers. The sequence starts like this: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,…

The formula to calculate the nth fibonacci number is to sum the two previous fibonacci numbers.

• F(0) = 0 and F(1) = 1 (base case)
• F(n) = F(n - 1) + F(n - 2) (recursive case)

Example: Fibonacci Tree Recursion

• Here, we are calling the function twice in the last line, resulting in the tree with two branches.

# Recursive implementation to calculate the n-th Fibonacci number
def fibonacci(n):
    # Base case: n = 0 or 1
    if n <= 1:
        return n

    # Recursive case: fib(n) = fib(n - 1) + fib(n - 2)
    return fibonacci(n - 1) + fibonacci(n - 2)

• To calculate fibonacci(5), we get fibonacci(4) + fibonacci(3).
• Now, both of these will execute within their own function calls.
  • fibonacci(4) will call fibonacci(3) + fibonacci(2) and so on, until n hits 1 or 0
• After that it will return the result, and keep going back up all the way until fibonacci(4) which will give us an answer of 3.
• Now, we have the answer to fibonacci(4) and do the same for fibonacci(3) which results in 22.
• Add the two together, and the 5th fibonacci number is 5.

2. Iteration and Recursion

While this recursive implementation is fine, it's not efficient for large values of n because it recalculates the same Fibonacci numbers many times. For example, to calculate F(5), we calculate F(3) twice. This redundancy grows exponentially with n.

In practice, we often use dynamic programming or iteration to optimize this calculation:

The underscore _ in a for loop is a convention that indicates we're using a loop counter variable that we don't actually need to reference within the loop

def fibonacci_optimized(n):
    if n <= 1:
        return n
    
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

This iterative version has O(n) time complexity instead of O(2^n).

Summary

a. Time Complexity

Let’s look at the number of nodes on each level. The pattern here is, each level has the potential to hold 2 times the nodes of the previous levels.

→ A reasonable upper-bound for the total number of nodes in the tree is 1 + 2 + 4 + 8 + … + 2^n. The sum of the series is roughly 2^(n+1) - 1.

This means that the total number of nodes in the tree is O(2^n).  Each node itself is a function call and simply calculates the sum of two values, thus the time complexity of the function is O(2^n).

b. Space Complexity

For the recursive Fibonacci implementation, the space complexity is O(n) due to the function call stack. Despite having O(2^n) total function calls, the maximum depth of the recursion tree is n, and at any point, we only need to store at most n function calls on the stack.

For the optimized iterative version, the space complexity is O(1) since we only need two variables (prev and curr) regardless of the input size.